﻿#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <numeric>

using namespace std;
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	
};

class Solution {
public:
	int repeatedStringMatch(string a, string b) {
		int i = 0;
		int j = 0;
		if (b.size() == 0)
			return 0;
		int count = b.size() % a.size() == 0 ? b.size() / a.size() : b.size() / a.size() + 1;
		bool started = false;
		string test;
		for (int k = 0; k < count; k++) { test += a; }
		while (j < b.size()) {
			if (test[i] != b[i]) {
				if (started) {
					count = -1;
					break;
				}
				else
					i++;
			}
			else {
				started = true;
				i++;
				j++;
			}
		}
		if (count != -1 && j >= b.size())
			return count;
		test += a;
		while (j < b.size()) {
			if (test[i] != b[i]) {
				if (started) {
					count = -1;
					break;
				}
				else
					i++;
			}
			else {
				started = true;
				i++;
				j++;
			}
		}
		return count;
	}
};

int main()
{ 
	Solution sol;
	sol.repeatedStringMatch("aaac","aac");

	cout <<endl;
}
